class Solution {
public:
    vector<string> result;
    vector<int> segement;

    void Deal(string& s) {
        string str;
        for (int i = 0; i < 3; i++) {
            str += s.substr(segement[i], segement[i + 1] - segement[i]);
            str += ".";
        }
        str += s.substr(segement[3]);
        result.push_back(str);
    }

    void restoreIpAddresses(string& s, int cur, int num) {
        if (cur >= s.size() && num != 4) return;
        if (cur < s.size() && num > 4) return;
        if (cur == s.size() && num == 4)  {
            Deal(s);
            return;
        }

        if (s[cur] == '0') {
            segement.push_back(cur);
            restoreIpAddresses(s, cur + 1, num + 1);
            segement.pop_back();
        }
        else {
            segement.push_back(cur);
            restoreIpAddresses(s, cur + 1, num + 1);
            restoreIpAddresses(s, cur + 2, num + 1);
            if (cur + 3 <= s.size() && s.substr(cur, 3) <= "255") 
                restoreIpAddresses(s, cur + 3, num + 1);
            segement.pop_back();
        }
    }
    vector<string> restoreIpAddresses(string s) {
        restoreIpAddresses(s, 0, 0);
        return result;
    }
};
